In some mobile communication systems, maximum likelihood decoding is used for error correction in the communication pathway (see Patent Document 1, for example). Maximum likelihood decoding will be described hereinafter using a specific example.
The convolution encoder 100 shown in FIG. 3 is used for generating a convolution code. The convolution encoder 100 is composed of a bit register G100, a bit register G101, a mod2 adder S100, and a mod2 adder S101. In a mobile communication system, a transmission device for transmitting data, and a receiving device for receiving data both have the convolution encoder 100.
In the convolution encoder 100, when the one-bit bit values (input values) shown in Table 1 are inputted in sequence, the bit value stored in the bit register G100, the bit value stored in the bit register G101, and the outputted bit sequence (output value) each change as shown in Table 1. In the initial state of the convolution encoder 100, the bit values stored by the bit register G100 and the bit register G101 are both assumed to be “0.”
TABLE 1INPUT VALUENo(TRANSMISSION DATA)G100G101OUTPUT VALUE(INITIAL STATE)0011101 121111 030011 040001 151101 160010 1
The transmission device inputs the transmission data as an input value to the convolution encoder 100. The transmission device then transmits the output value from the convolution encoder 100 to the receiving device. This output value is determined based on a prior input value (two bits in FIG. 3) (this determination is referred to as convolution of the prior input value).
A description will be given hereinafter using a specific example. In this specific example, the transmission device sequentially transmits the first through fourth output values “11,” “10,” “10,” and “11” shown in Table 1 as transmission data. A one-bit error occurs in the third transmission data during communication, and the receiving device receives the bit sequence “11,” “10,” “11,” “11” in sequence.
Table 2 is a table showing the processing performed when the first transmission data are received. The receiving device inputs the acquired input values “0” and “1” to the convolution encoder 100 in the initial state of Table 1. The receiving device then computes the Hamming distance between the received bit sequence (reception value) “11” and the output values “00” and “11” outputted from the convolution encoder 100. The receiving device then acquires as the first reception data the input value “1” corresponding to the data having the smallest value (“11” in this case) in the computed Hamming distance. Since it is assumed that there is no error in the first reception data, the acquired first reception data naturally match the first transmission data.
TABLE 2INPUTOUTPUTRECEPTIONHUMMINGVALUEG100G101VALUEVALUEDISTANCE(INITIAL00STATE)0000 01 121101 10
Table 3 is a table showing the showing the processing performed when the receiving device receives the second transmission data. The receiving device inputs the acquired input values “0” and “1” to the convolution encoder 100 that is in the state (most recent state) corresponding to the input value “1” of Table 2. The receiving device then computes the Humming distance between the reception value “10” and the output values “01” and “10” outputted from the convolution encoder 100.
The receiving device furthermore computes the total Humming distance for each state transition of the output value from the initial state. The output value corresponding to the first reception data in this case is determined to be “11,” and the state transition is therefore any of “11” to “01,” and “11” to “10.” The total Humming distances that correspond to these state transitions are 2 and 0, respectively. The receiving device acquires as the second reception data the input value “1” that corresponds to the smallest value of the total Humming distance (“11” to “10” in this case) among the state transitions. Since it is assumed that there is no error in the second reception data, the acquired second reception data naturally match the second transmission data.
TABLE 3INPUTOUTPUTRECEPTIONHUMMINGVALUEG100G101VALUEVALUEDISTANCE(MOST10RECENTSTATE)0010 11 021111 00
Table 4 is a table showing the showing the processing performed when the receiving device receives the third transmission data. The receiving device inputs the acquired input values “0” and “1” to the convolution encoder 100 that is in the state (most recent state) corresponding to the input value “1” of Table 3. The Humming distance is then computed between the reception value “11” and the output values “01” and “10” acquired as a result.
The receiving device furthermore computes the total Humming distance for each state transition of the output value from the initial state. The output values corresponding to the first and second reception data in this case are determined to be “11” and “10,” respectively, and the state transition is therefore any of “11” to “10” to “01”, and “11” to “10” to “10.” The total Humming distances that correspond to these state transitions are 1 and 1, respectively. In this case, since the total Humming distances are the same, the receiving device cannot determine the third reception data.
TABLE 4INPUTOUTPUTRECEPTIONHUMMINGVALUEG100G101VALVEVALUEDISTANCE(MOST10RECENTSTATE)0010 11 111111 01
Table 5 is a table showing the showing the processing performed when the receiving device receives the fourth transmission data. Since the third reception data are not determined, the receiving device inputs the acquired input values “0” and “1” to the convolution encoder 100 that is in a plurality of states (most recent state) respectively corresponding to the input values “0” and “1” of Table 4. The receiving device then computes the Humming distance between the reception value “11” and each output value outputted from the convolution encoder 100.
The receiving device furthermore computes the total Humming distance for each state transition of the output value from the initial state. The output values corresponding to the first and second reception data in this case are determined to be “11” and “10,” respectively, and the state transition is therefore any of the four transitions that include “11” to “10” to “01” to “11,” “11” to “10” to “01” to “00,” “11,” to “10” to “10” to “10,” and “11” to “10” to “10” to “01.” The total Humming distances that correspond to these state transitions are 1, 3, 2, and 2 respectively. The receiving device acquires as the third and fourth reception data the third input value “0” and the fourth input value “0” that respectively correspond to the smallest value of the total Humming distance (“11” to “10” to “01” to “11” in this case) among the state transitions. Since it is assumed that there is no error in the second reception data, the acquired second reception data naturally match the second transmission data.
TABLE 5INPUTOUTPUTRECEPTIONHUMMINGVALUEG100G101VALUEVALUEDISTANCE(MOST01RECENTSTATE)0001 11 101100 02(MOST11RECENTSTATE)0011 01 111110 11
Patent Document 1: Japanese Laid-open Patent Application No. 2005-294898